package leetcode_1_200;

import node.ListNode;

public class LeeCode_148 {
    public static void main(String[] args) {
//        ListNode res1 = sortList(new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3)))));
//        System.out.println(res1);
//        ListNode res2 = sortList(new ListNode(-1, new ListNode(5, new ListNode(3, new ListNode(
//                4, new ListNode(0))))));
//        System.out.println(res2);
        System.out.println(sortList(new ListNode(3, new ListNode(4, new ListNode(1)))));
    }
    private static ListNode sortList(ListNode head) {
        if (head == null){
            return null;
        }
        if (head.next == null)
            return head;
        if (head.next.next == null){
            ListNode next = head.next;
            if (head.val > next.val){
                next.next = head;
                head.next = null;
                return next;
            }
            return head;
        }
        ListNode slow = head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode quick = head;
        while (quick != null){
            slow = slow.next;
            pre = pre.next;
            if (quick.next == null){
                quick = null;
                continue;
            }
            quick = quick.next.next;
        }
        pre.next = null;
        ListNode preL = sortList(slow);
        ListNode aftL = sortList(head);
        ListNode curL = preL;
        ListNode curR = aftL;
        ListNode now;
        if (curL.val > curR.val){
            dummy.next = curR;
            now = curR;
            curR = curR.next;
        }else {
            dummy.next = curL;
            now = curL;
            curL = curL.next;
        }
        while (curL != null && curR != null){
            if (curL.val > curR.val){
                now.next = curR;
                now = curR;
                curR = curR.next;
                continue;
            }
            now.next = curL;
            now = curL;
            curL = curL.next;
        }
        while (curL != null){
            now.next = curL;
            now = curL;
            curL = curL.next;
        }
        while (curR != null){
            now.next = curR;
            now = curR;
            curR = curR.next;
        }
        return dummy.next;
    }
}
